package sjg.DataStructures.sort;

/**
 * 选择排序
 * #### 思路：
 * 1. 从数组取最小值与第一位交换位置
 * 2. 从剩余数组取最小值与第二位交换位置
 * 3. 重复上述步骤，直到有序
 */
public class SelectSort {
    public static void main(String[] args) {
        System.out.println("￥￥￥￥￥￥￥￥ Select sort begin ￥￥￥￥￥￥￥￥");
        int[] arr = {312, 1234, 1, 234, 1, 2, 432, -100};
        print(arr);
        selectSort(arr);
        System.out.println("￥￥￥￥￥￥￥￥ Select sort over ￥￥￥￥￥￥￥￥");
        print(arr);
    }

    private static void print(int[] arr) {
        for (int i : arr) {
            System.out.printf("%d\t", i);
        }
        System.out.println();
    }

    // 选择排序
    private static void selectSort(int[] arr) {
        // 判空
        if (arr == null || arr.length == 0) {
            System.out.println("arr is null...");
        }
        int minValSubscript = 0;
        int minVal;
        int temp;
        for (int i = 0; i < arr.length - 1; i++) {
            minVal = arr[i];
            for (int j = i; j < arr.length; j++) {
                if (minVal > arr[j]) {
                    minVal = arr[j];
                    minValSubscript = j;
                }
            }
            // 交换值 minValSubscript 和 i下标 换值
            temp = arr[i];
            arr[i] = arr[minValSubscript];
            arr[minValSubscript] = temp;
        }
    }
}
